Image pyramids provide an efficient means for the storage and retrieval of digital images at various resolutions. It is customary in such hierarchical image storage and retrieval systems to construct a multiple of image resolutions by repeatedly filtering and subsampling a high resolution image using a scheme similar to the teachings found in the patent to Melnychuck and Jones (U.S. Pat. No. 4,969,204). In such cases, the higher resolution components are usually stored in the form of quantized residuals that are entropy encoded to save storage space. In the context of the present invention, we will make reference to one such system, namely the Kodak Photo CD system, as an example to demonstrate the fundamental concepts underlying the invention. However, it should be noted that this example is only used to give the reader an insight as to the operation of one or more embodiments of the invention with the understanding that other hierarchical image storage and retrieval systems with other resolutions or arrangements that store the high resolution components as residuals may be chosen to suit specific needs without detracting from the teachings of the present invention.
The Kodak Photo CD system is composed of an image hierarchy or pyramid in which the highest resolution image contains 3072.times.2048 pixels and is referred to as the 16BASE image. This resolution is in most cases adequate to produce photographic quality originals on an appropriate digital output device. The next level of hierarchy, referred to as the 4BASE, is composed of 1536.times.1024 pixels and is adequate to generate a high quality HDTV display, or a small-sized photographic quality print on an appropriate digital output device. The lower resolution levels are, respectively, the BASE image consisting of 768.times.512 pixels (suitable for NTSC/PAL/SECAM television viewing), the BASE/4 image consisting of 384.times.256 pixels (suitable for sub-NTSC displays), and the BASE/16 consisting of 192.times.128 pixels (suitable for displaying thumbnail images). The complete image hierarchy is constructed from the 16BASE image using the teachings found in the #204 patent to Melnychuck and Jones previously cited. The BASE/16, BASE/4, and the BASE images are stored onto a digital storage medium such as a CD in uncompressed form while the 4BASE and 16BASE images are represented as residuals and are quantized and compressed by using entropy coding prior to their storage on the CD.
A quantizer is a many-to-one mapping and, as such, the quantized data often contains degradations compared to the original unquantized data. The degradations can be particularly significant when the input data has a distribution (histogram) containing long tails, as those values are clipped to the outermost quantization level. In a hierarchical imaging system such as the Kodak Photo CD system, the residual image usually has a symmetric distribution with a high peak and decaying tails, sometimes approximated by a Laplacian (two-sided exponential) distribution. The minimum-mean-squared-error quantizer that accommodates such a distribution contains dense inner level (in the region where the signal peaks) and sparse outer level (around the tails). An example of how a quantizer processes treats signal values is shown in the table of FIG. 10. It is based on the principal that by introducing a larger error in those values where the signal occurs infrequently and a smaller error at values where it occurs more frequently, the overall average error can be minimized.
As described in the teachings of the previously cited patent to Melnychuck and Jones, the construction of a high-resolution image is accomplished by adding the quantized residual to the interpolated low-resolution component from the previous stage. Thus, the error resulting from the quantization of the residual is propagated to the higher-resolution images. Although the residuals with large magnitudes occur infrequently, it should be noted that they often represent high-contrast edges or details in an image, and the introduction of a large quantization error can create an annoying visual artifact or loss of detail in the high-resolution image. One of the objectives of the present invention is to introduce a method whereby the low-resolution image whose image quality is less critical can be modified in order to minimize the quantization errors in the high-resolution image.
The aforementioned hierarchical storage technique is combinable with the insertion and removal of a digital watermark according to the teachings of the cited Rabbani et al., application to form a distributed image system. In a distributed image system it is common to deliver an image of compromised image quality for the purposes of browsing or proofing. The compromise can be made with the use of a removable watermark. Primary use of such a system is by professional portrait photographers who distribute a plurality of images to a customer for selection and approval. The watermark is a form of graphic overlay that may contain a copyright notice or information regarding the restricted use of the image.
Upon selection of the desired image by the customer, the professional delivers a high quality rendition of the image either digitally or in hard copy form without the watermark. At all times the professional possesses the sole means of generating and delivering unmarked high quality images. In a conventional photographic system the means for generating would be the original negatives of the images; in a digital hierarchical system according to the invention of Rabbani et al., the means for generating are higher resolution residual components.
In a digital imaging system, and in particular one that includes a hierarchical form of digital storage and retrieval, the professional may use a suitable digital storage medium such as a CD for the distribution of proofs. In an unrestricted environment, the customer may choose a desired image resolution from the hierarchy for the purposes of browsing, proofing, or hard copy fulfillment. In those instances where it is desirable for the professional to deliver the digital storage medium containing the entire image hierarchy to the customer, it is also most economical to record the entire image hierarchy once onto the digital storage medium and avoid having to make a second copy containing only low resolution components for distribution. However, it is also desirable to restrict the use of selected high resolution components for the purpose of full image quality fulfillment until payment has been received.
The invention of the Rabbani et al. application, previously referenced, teaches a method whereby the professional places a digital watermark on a selected image component. The removal of the watermark is done through an additional image component containing the reverse of the watermark. The customer, having possession of the CD storage medium, would possess the means for generating his own high quality hard copy when authorized by the professional.
When a watermark is applied to a low-resolution image, the pixel values in that region of the low-resolution image affected by the watermark can become completely different from the pixel values in the high-resolution image corresponding to the same region. As a result, in those regions, the difference between the interpolated watermarked image and the high-resolution image can become fairly large which, given the nature of the quantizer, can result in large quantization errors. These errors often appear as a visual trace of the watermark in the high-resolution image and significantly impair the visual quality of the high-resolution image. Minimization of such errors is addressed by the present invention.